package leetcode101.ch3;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

//LC 340 至多包含 K 个不同字符的最长子串
public class LengthOfLongestSubstringKDistinct {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s.length() <= k) {
            return s.length();
        }

        Map<Character, Integer> map = new HashMap<>();
        int length = 0;
        for (int l = 0, r = 0; r < s.length() ; r++) {
            map.put(s.charAt(r), r);
            if (map.size() > k) {
                int leftIdx = Collections.min(map.values());
                map.remove(s.charAt(leftIdx));
                l = leftIdx + 1;
            }else {
                length = Math.max(length, r - l + 1);
            }
        }
        return length;
    }

    public static void main(String[] args) {
        new LengthOfLongestSubstringKDistinct().lengthOfLongestSubstringKDistinct("abee", 1);
    }
}
